package leetcode.code0436;

import java.util.Arrays;

import leetcode.IDebug;




//执行用时：8 ms, 在所有 Java 提交中击败了98.04%的用户
//
//内存消耗：46.4 MB, 在所有 Java 提交中击败了25.21%的用户
//
//通过测试用例：19 / 19
public class Solution implements IDebug {

	public int[] findRightInterval(int[][] intervals) {
		int len = intervals.length;
		int[] ans = new int[len];
		int[][] info = new int[len][2];
		for (int i = 0; i < len; i++) {
			info[i][0] = intervals[i][0];
			info[i][1] = i;
		}
		Arrays.sort(info, (a, b) -> a[0] - b[0]);
		for (int i = 0; i < len; i++) {
			int find = intervals[i][1];
			int l = 0, r = len - 1;
			int cur = -1;
			while (l <= r) {
				int m = l + ((r - l) >> 1);
				int[] ifo = info[m];
				if (ifo[0] == find) {
					cur = ifo[1];
					break;
				} else if (ifo[0] > find) {
					cur = ifo[1];
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
			ans[i] = cur;
		}
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
